package leetcode.primary;

public class T53 {
    int len;
    int[] prefix;
    public int maxSubArray(int[] nums) {
        len= nums.length;
        prefix = new int[len+1];
        int left=len-1;
        int right = 0;
        int max = -100001;

        for (int i=1;i<len+1;i++){
            prefix[i] = prefix[i-1]+nums[i-1];
            System.out.print(prefix[i]+" ");
            if (prefix[i]>max){
                right = i;
                max = prefix[i];
            }
        }
        System.out.println();

        max = prefix[len]-prefix[len-1];
        for (int i=len-1;i>=0;i--){
            if (prefix[len]-prefix[i]>max){
                left = i;
                max = prefix[len]-prefix[i];
            }
        }

        System.out.println("left="+left+" right="+right);
        if (right>left){
            return prefix[right]-prefix[left];
        }else {
            return nums[right-1];
        }

    }

    public static void main(String[] args) {
        T53 test = new T53();
        int subArray = test.maxSubArray(new int[]{0,-3,1,1});
        System.out.println(subArray);
    }
}
